class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ret=[[]]
        n=len(nums)
        route=[]
        def dfs(index,route):
            ret.append(route[:])
            for i in range(index,n):
                if i==index or nums[i]!=nums[i-1]:
                    route.append(nums[i])
                    dfs(i+1,route)
                    route.pop()
        for j in range(n):
            if j==0 or nums[j]!=nums[j-1]:
                route.append(nums[j])
                dfs(j+1,route)
                route.pop()
        return ret


s=Solution()
print(s.subsetsWithDup([1,2,3,4,5]))


# 执行用时：
# 36 ms
# , 在所有 Python3 提交中击败了
# 90.27%
# 的用户
# 内存消耗：
# 15.1 MB
# , 在所有 Python3 提交中击败了
# 45.88%
# 的用户